#include "tools.h"
#include <deque>
using std::deque;

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;

        queue<TreeNode*> q;
        q.push(root);
        int flag = 0;
        while(!q.empty()){
            deque<int> level;
            int n = q.size();
            for(int i = 0; i < n; ++i){
                TreeNode* node = q.front();
                q.pop();
                if(flag % 2 == 0) level.push_back(node->val);
                else level.push_front(node->val);

                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.emplace_back(vector<int>{level.begin(), level.end()});
            ++flag;
        }
        return res;
    }
};


int main(int argc, char const *argv[])
{
    int arr[7] = {3,9,20,-1,-1,15,7};
    TreeNode* tree = create_tree(arr, 7);

    Solution s;
    vector<vector<int>> res = s.zigzagLevelOrder(tree);

    for(int i=0; i < res.size(); ++i){
        vector<int> level = res[i];
        for(int j = 0; j < level.size(); ++j){
            cout << level[j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

